package likou;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/29 10:38
 */
public class _327 {
    public int countRangeSum(int[] nums, int lower, int upper) {
        long s = 0;
        long[] sum = new long[nums.length + 1];
        //当sum[i]-sum[j] ∈ [lower,upper]，则算得上是一个解，解的区间为j+1,j+2...i-1,i
        for (int i = 0; i < nums.length; ++i) {
            s += nums[i];
            sum[i + 1] = s;
        }
        long[] sorted = new long[sum.length / 2 + 1];
        return countRangeSumRecursive(sum, sorted, lower, upper, 0, sum.length - 1);
    }

    public int countRangeSumRecursive(long[] sum, long[] sorted, int lower, int upper, int left, int right) {
        if (left == right) {
            return 0;
        } else {
            int mid = (left + right) / 2;
            int n1 = countRangeSumRecursive(sum, sorted, lower, upper, left, mid);
            int n2 = countRangeSumRecursive(sum, sorted, lower, upper, mid + 1, right);
            int ret = n1 + n2;

            // 首先统计下标对的数量
            int i = left;
            int l = mid + 1;
            int r = mid + 1;
            //区间分为两部分，前面部分i 在后面部分l、r找合适的解
            while (i <= mid) {
                while (l <= right && sum[l] - sum[i] < lower) {
                    l++;
                }
                while (r <= right && sum[r] - sum[i] <= upper) {
                    r++;
                }
                ret += r - l;
                i++;
            }

            // 随后合并两个排序数组
            System.arraycopy(sum, left, sorted, 0, mid - left + 1);
            i = 0;
            int bright = mid - left;//buffer里面的最大下标
            int j = mid + 1;
            int k = left;
            //排序有利于上面的while操作，即所有较小的，放在前面，较大的放在后面，便于while的结束。
            //一个归并分支的前面部分和后面部分排序
            while (i <= bright && j <= right) {
                //只能保证前面部分对于后面的部分是有序的，每次这样之后，后面的部分全是有序，前面部分也全部有序
                if (sorted[i] < sum[j]) {
                    sum[k++] = sorted[i++];
                } else {
                    sum[k++] = sum[j++];
                }
            }
            while (i <= bright) {
                sum[k] = sorted[i];
                k++;
                i++;
            }
            return ret;
        }
    }
}
